Meeting rooms II

Time: O(NlogN); Space: O(N); medium

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: intervals: [0, 30],[5, 10],[15, 20]

Output: 2

Example 2:

Input: intervals: [7,10], [2,4]

Output: 1

Note:

  • Input types have been changed on April 15, 2019.

Please reset to default code definition to get new method signature.

[1]:

class Interval:
    """
    Definition for an interval
    """
    def __init__(self, start=0, end=0):
        self.start = start
        self.end = end

[3]:

class Solution1(object):
    def minMeetingRooms(self, intervals):
        '''
        :type intervals: [Interval[]]
        :rtype: bool
        '''
        starts, ends = [], []
        for i in intervals:
            starts.append(i.start)
            ends.append(i.end)

        starts.sort()
        ends.sort()

        s, e = 0, 0
        min_rooms, cnt_rooms = 0, 0
        while s < len(starts):
            if starts[s] < ends[e]:
                cnt_rooms += 1  # Acquire a room.
                # Update the min number of rooms.
                min_rooms = max(min_rooms, cnt_rooms)
                s += 1
            else:
                cnt_rooms -= 1  # Release a room.
                e += 1

        return min_rooms

[4]:

s = Solution1()
a1 = Interval(0, 30)
a2 = Interval(5, 10)
a3 = Interval(15, 20)
assert s.minMeetingRooms([a1, a2, a3]) == 2

a1 = Interval(7,10)
a2 = Interval(2, 4)
assert s.minMeetingRooms([a1, a2, a3]) == 1